package cn.aylog.example;

/**
 * 普林姆算法解决修路问题
 * 从当前已到达的节点中寻找下一个最近的点
 */
public class PrimeAlgorithm {
    public static void main(String[] args) {
        char[] nodes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int n = nodes.length;
        int NONE = Integer.MAX_VALUE;
        int[][] links = {
                {NONE, 5, 7, NONE, NONE, NONE, 2},
                {5, NONE, NONE, 9, NONE, NONE, 3},
                {7, NONE, NONE, NONE, 8, NONE, NONE},
                {NONE, 9, NONE, NONE, NONE, 4, NONE},
                {NONE, NONE, 8, NONE, NONE, 5, 4},
                {NONE, NONE, NONE, 4, 5, NONE, 6},
                {2, 3, NONE, NONE, 4, 6, NONE}
        };
        prime(n, nodes, links, 5);
    }

    public static void prime(int nNode, char[] nodes, int[][] link, int startNode) {
        boolean[] visited = new boolean[nNode]; // 用于记录节点是否被访问
        visited[startNode] = true; // 标记起始节点被访问
        int from = -1, to = -1, min = Integer.MAX_VALUE;
        // 遍历未访问节点
        for (int v = 1; v < nNode; v++) {
            // 遍历节点
            for (int x = 0; x < nNode; x++) {
                for (int y = 0; y < nNode; y++) {
                    // 获取下一个最近的未访问节点
                    if (visited[x] && !visited[y] && link[x][y] < min) {
                        from = x;
                        to = y;
                        min = link[x][y];
                    }
                }
            }
            // 输出当前选中路径
            System.out.printf("<%s,%s> %d\n", nodes[from], nodes[to], min);
            // 重置
            min = Integer.MAX_VALUE;
            // 标记节点为已访问
            visited[to] = true;
        }
    }
}
